"""
给定一个可能有重复数字的整数数组candidates和一个目标数target，
找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

示例1:
输入: candidates =[10,1,2,7,6,1,5], target =8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例2:
输入: candidates =[2,5,2,1,2], target =5,
输出:
[
[1,2,2],
[5]
]

链接：https://leetcode-cn.com/problems/4sjJUc
"""
from mode import *


class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        ans = []
        candidates.sort()
        temp = []

        def dfs(candidate, idx, target):
            if target == 0:
                ans.append(list(temp))
                return
            for i in range(idx, n):
                if candidate[i] > target:
                    break
                if i > idx and candidate[i] == candidate[i - 1]:
                    continue
                temp.append(candidate[i])
                dfs(candidate, i + 1, target - candidate[i])
                temp.pop()

        dfs(candidates, 0, target)
        return ans


if __name__ == "__main__":
    A = Solution()
    print(A.combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
